#include<vector>
using namespace std;

 struct ListNode {
    int val;
   ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
 };
 
class Solution {
private:

    ListNode* reverse(ListNode* root) {
        if (root == NULL || root->next == NULL) return root;
        ListNode* prev = NULL;
        ListNode* cur = root;
        while (cur != NULL) {
            auto tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        l1 = reverse(l1);
        l2 = reverse(l2);
        int add = 0;
        auto head = l1;
        ListNode* prev = head;
        while (l1!= NULL && l2!= NULL) {
            l1->val += l2->val + add;
            add = l1->val / 10;
            l1->val %= 10;
            prev = l1;
            l1 = l1->next;
            l2 = l2->next;
        }
        if (l2 != NULL) 
            prev->next = l2;
        while (add > 0 && prev->next != NULL) {
            prev->next->val += add;
            add = prev->next->val / 10;
            prev->next->val %= 10;
            prev = prev->next;
        }
        if (add > 0) 
            prev->next = new ListNode(add);
        return reverse(head);
    }
};